//
// Created by YXH on 2023/3/21.
//
#include <stdio.h>/*该文件包含pringtf()等函数*/
#include <stdlib.h>/*该文件包含exit()等函数*/
#include <malloc.h>/*该文件包含malloc()等函数*/
#include <fci.h>

typedef int DataType;/*定义DataType为int*/


typedef struct Node {
    DataType data;
    struct Node *next;
} LNode;

/*单链表初始化。初始化成功函数返回0，否则返回1。*/
int ListInitiate(LNode **head) {
    LNode *p = NULL;
    LNode *temp = (LNode *) malloc(sizeof(LNode));
    if (temp == NULL) {
        return 1;
    }
    temp->data = 0;
    temp->next = NULL;
    return 0;
}

/* 函数返回由head所表示的单链表的长度。*/
int ListLength(LNode *head) {
    if (head == NULL) {
        return (int) NULL;
    }
    int len = 0;
    LNode *temp = head;
    while (temp != NULL) {
        len++;
        temp = temp->next;
    }
    return len;
}

// 在由head所表示的单链表里插入一个元素 x 到位置 i。
// 插入成功函数返回0，否则返回1。
int ListInsert(LNode *head, int i, DataType x) {
    int j;
    LNode *abc = NULL;
    LNode *temp = head;
    if (i == 0) {
        temp->data = x;
        return 0;
    }
    for (j = 1; j < ListLength(head); j++) {
        temp = temp->next;
        if (temp == NULL) {
            return 1;
        }
    }
    abc = (LNode *) malloc(sizeof(LNode));
    abc->data = x;
    abc->next = temp->next;
    temp->next = abc;
    return 0;
}

// 在由head所表示的单链表里删除位置 i 上的元素并将其值存入 x 变量里。调用成功后，列表长度减1。
int ListDelete(LNode *head, int i, DataType *x) {
    LNode *del = NULL;
    LNode *temp = head;
    int j = 0;
    while (temp->next && j < i) {
        temp = temp->next;
        j++;
    }
    if (!(temp->next && j > i - 1)) {
        return 1;
    }
    del = temp->next;
    temp->next = del->next;
    *x = del->data;
    free(del);
    return 0;
}


// 在由head所表示的单链表里获取位置 i 上的元素并将其值存入 x 变量里。调用成功后，列表长度不变。
int ListGet(LNode *head, int i, DataType *x) {
    LNode *temp = head;
    int len = ListLength(head);
    for (int j = 0; j < len; j++) {
        if (j == i) {
            break;
        }
        temp = temp->next;
    }
    *x = temp->data;
    return 0;
}

// 释放所有的由head所表示的单链表里的元素节点（含头结点）。当释放完全成功时，函数返回0，否则返回1。
int Destroy(LNode **head) {
    if (*head == NULL) {
        return 0;
    }
    LNode *temp = *head;
    *head = temp->next;
    free(temp);
    return 0;
}

LNode ListAdd(LNode **head1, LNode **head2) {
    struct Node head;
    ListInitiate((LNode **) &head);
    int a = ListLength(*head1);
    int b = ListLength(*head2);
    _Bool T = TRUE;
    _Bool U = TRUE;
    _Bool P = TRUE;
    _Bool O = TRUE;
    //有序合并
    int i = 0, x, y, A = 0, B = 0, X, Y;
    while (T) {
        while (U) {
            X = ListGet(*head1, A, &x);
            if (A == a) {
                U = FALSE;
            }
        }
        while (P) {
            Y = ListGet(*head1, A, &x);
            if (B == b) {
                P = FALSE;
            }
        }
        for (int j = 0; j < a+b; ++j) {
            ListInsert(&head, j, (X < Y) ? X : Y);
        }
        O = (X < Y) ? TRUE : FALSE;
        if (O) {
            A++;
        } else { B++; }

        if (i == a + b) {
            T = FALSE;
        }
    }
    return head;
}

void ListPrintf(LNode *head) {
    int x;
    for (int i = 0; i < ListLength(head); ++i) {
        ListGet(head, i, &x);
        printf("%d ", x);
    }
    printf("\n");
}
int main() {
    LNode *head1;
    LNode *head2;
    LNode *head3;
    ListInitiate(&head1);
    ListInitiate(&head2);
    for (int i = 0; i < 10; i++) {
        ListInsert(head1, i, i+1);
    }
    ListPrintf(head1);

    for (int j = 0; j < 10; j++) {
        ListInsert(head2, j, j+2);
    }
    ListPrintf(head2);

//    *head3=ListAdd(&head1,&head2);
//    ListPrintf(head3);
}
